// Time:  O(n)
// Space: O(w)

#include <head/TreeNode.h>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        vector<TreeNode *> q = {root};
        bool is_odd = false;
        while (!empty(q)) {
            vector<TreeNode *> new_q;
            TreeNode *prev = nullptr;
            for (const auto& node : q) {
                if (is_odd) {
                    if (node->val % 2 || (prev && prev->val <= node->val)) {
                        return false;
                    }
                } else {
                    if (node->val % 2 == 0 || (prev && prev->val >= node->val)) {
                        return false;
                    }
                }
                if (node->left) {
                    new_q.emplace_back(node->left);
                }
                if (node->right) {
                    new_q.emplace_back(node->right);
                }
                prev = node;
            }
            q = move(new_q);
            is_odd = !is_odd;
        }
        return true;
    }
};


class Solution2 {
public:
    bool isEvenOddTree(TreeNode* root) {
        if(!root) {
            return true;
        }

        queue<TreeNode*> q;
        int level = 0;

        q.push(root);

        while(!q.empty()) {
            int size = q.size();
            int prev = (level % 2 == 0) ? INT_MIN : INT_MAX;

            for(int i=0; i<size; i++) {
                TreeNode* node = q.front();
                q.pop();

                if((level % 2 == 0 && (node->val % 2 == 0 || node->val <= prev)) ||
                   (level % 2 == 1 && (node->val % 2 == 1 || node->val >= prev))) {
                    return false;
                }

                prev = node->val;

                // Push the children to the queue
                if(node->left) {
                    q.push(node->left);
                }

                if(node->right) {
                    q.push(node->right);
                }
            }

            level++;
        }
        return true;
    }
};